package leetcode.dandiaostack;

import java.util.Arrays;
import java.util.Stack;

public class Test4 {
    public static void main(String[] args) {
        int[] temperatures = {1, 2, 3, 4, 3};
        int[] ints = nextGreaterElements(temperatures);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }
    }

    public static int[] nextGreaterElements(int[] nums) {
        int length = nums.length;
        int[] result = new int[length];
        Arrays.fill(result, -1);
        Stack<Integer> stack = new Stack<>();
//        for (int i = length * 2 - 1; i >= 0; i--) {
//            int x = nums[i % length];
//            while (!stack.isEmpty() && x >= stack.peek()) {
//                stack.pop();
//            }
//            if (i < length && !stack.isEmpty()) {
//                result[i] = stack.peek();
//            }
//            stack.push(x);
//        }

        for (int i = 0; i < length * 2; i++) {
            int x = nums[i % length];
            while (!stack.isEmpty() && x > nums[stack.peek()]) {
                result[stack.pop()] = x;
            }
            if (i < length) {
                stack.push(i);
            }
        }
        return result;
    }
}
